#include <iostream>
#include <stack>

template<class T = int>
class BitNode {
  public:
    explicit BitNode(T _data) : data(_data), lchild(nullptr), rchild(nullptr), parent(nullptr) {}
    virtual ~BitNode() = default;

  public:
    BitNode<T>* parent;
    T data;
    BitNode<T>* lchild;
    BitNode<T>* rchild;
};

template<class T = int>
void visitNode(BitNode<T>* tree) { if (tree != nullptr) std::cout << tree->data << " "; }

template<class T = int>
void setParent(BitNode<T>* target, BitNode<T>* parent)
{
  if (target != nullptr) {
    target->parent = parent;
  }
}

template<class T = int>
void freeBitNode(BitNode<T>* tree) {
  if (tree != nullptr) {
    freeBitNode(tree->lchild);
    freeBitNode(tree->rchild);
    free(tree);
  }
}

template<class T = int>
void preRecurveOrder(BitNode<T>* tree)
{
  if (tree != nullptr) {
    visitNode(tree);
    preRecurveOrder(tree->lchild);
    preRecurveOrder(tree->rchild);
  }
}
template<class T = int>
void preLoopOrder(BitNode<T>* tree)
{
  using Node = BitNode<T>;
  std::stack<Node*> st;
  Node* p = tree;
  while (p != nullptr || !st.empty()) {
    if (p != nullptr) {
      visitNode(p);
      st.push(p);
      p = p->lchild;
    } else {
      p = st.top(); st.pop();
      p = p->rchild;
    }
  }
}

template<class T = int>
void inRecurveOrder(BitNode<T>* tree)
{
  if (tree != nullptr) {
    inRecurveOrder(tree->lchild);
    visitNode(tree);
    inRecurveOrder(tree->rchild);
  }
}
template<class T = int>
void inLoopOrder(BitNode<T>* tree)
{
  using Node = BitNode<T>;
  std::stack<Node*> st;
  Node* p = tree;
  while((p != nullptr) || !st.empty()) {
    if (p != nullptr) {
      st.push(p);
      p = p->lchild;
    } else {
      p = st.top(); st.pop();
      visitNode(p);
      p = p->rchild;
    }
  }
}

template<class T = int>
void postRecurveOrder(BitNode<T>* tree)
{
  if (tree != nullptr) {
    postRecurveOrder(tree->lchild);
    postRecurveOrder(tree->rchild);
    visitNode(tree);
  }
}
template<class T = int>
void postLoopOrder(BitNode<T>* tree)
{
  using Node = BitNode<T>;
  std::stack<Node*> st;
  Node* p = tree;
  Node* r = nullptr;
  while(p != nullptr || !st.empty()) {
    if (p != nullptr) {
      st.push(p);
      p = p->lchild;
    } else {
      p = st.top();
      if (p->rchild != nullptr && p->rchild != r) {
        p = p->rchild;
      } else {
        st.pop();
        visitNode(p);
        r = p;
        p = nullptr;
      }
    }
  }
}

#include<queue>
template<class T = int>
void levelOrderTr(BitNode<T>* tree)
{
  using Node = BitNode<T>;
  std::queue<Node*> que;
  Node* p = tree;
  que.push(p);
  while (!que.empty()) {
    p = que.front(); que.pop();
    visitNode(p);
    if (p->lchild != nullptr) {
      que.push(p->lchild);
    }
    if (p->rchild != nullptr) {
      que.push(p->rchild);
    }
  }
}

template<class T = int>
int getHightTr(BitNode<T>* tree)
{
  if (tree == nullptr) {
    return 0;
  }

  int lH = getHightTr(tree->lchild);
  int rH = getHightTr(tree->rchild);

  return 1 + (lH > rH ? lH : rH);
}

template<class T = int>
char getDepthTr(BitNode<T>* node)
{
  if (node == nullptr) {
    return 0;
  }

  char depth = 1;
  BitNode<T>* p = node->parent;
  while (p != nullptr) {
    p = p->parent;
    ++depth;
  }
  return depth;
}

template<class T = int>
int getBalanceTr(BitNode<T>* tree)
{
  if (tree == nullptr) {
    return 0;
  }
  int lH = getHightTr(tree->lchild);
  int rH = getHightTr(tree->rchild);
  
  return lH - rH;
}

// 在树根的前驱节点
template<class T = int>
BitNode<T>* searchPrecursor(BitNode<T>* root)
{
  if (root == nullptr) {
    return nullptr;
  }

  BitNode<T>* pre = root;
  BitNode<T>* p = root->lchild;
  while(p != nullptr) {
    pre = p;
    p = p->rchild;
  }
  return pre;
}

// 在树根的后继节点
template<class T = int>
BitNode<T>* searchSuccessor(BitNode<T>* root)
{
  if (root == nullptr) {
    return nullptr;
  }

  BitNode<T>* suc = root;
  BitNode<T>* p = root->rchild;
  while(p != nullptr) {
    suc = p;
    p = p->lchild;
  }
  return suc;
}

// 旋转函数设置节点的父节点即可，挂载点修改在函数外实现
template<class T = int>
BitNode<T>* leftRotate(BitNode<T>* target)
{
  if (target == nullptr || target->rchild == nullptr) {
    return target;
  }
  auto father = target->parent;
  auto new_tg = target->rchild;

  target->rchild = new_tg->lchild;
  if (new_tg->lchild != nullptr) {
    new_tg->lchild->parent = target;
  }

  new_tg->lchild = target;
  target->parent = new_tg;

  new_tg->parent = father;
  return new_tg;
}

template<class T = int>
BitNode<T>* rightRotate(BitNode<T>* target)
{
  if (target == nullptr || target->lchild == nullptr) {
    return target;
  }
  auto father = target->parent;
  auto new_tg = target->lchild;

  target->lchild = new_tg->rchild;
  if (new_tg->rchild != nullptr) {
    new_tg->rchild->parent = target;
  }

  new_tg->rchild = target;
  target->parent = new_tg;

  new_tg->parent = father;
  return new_tg;
}

